package m202405.d12;

import java.util.Stack;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/5/12 16:18
 */
public class Q19 {
    public static void main(String[] args) {
        ListNode list1 = new ListNode(1);
        Q19 q19 = new Q19();
        q19.removeNthFromEnd(list1, 1);
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode slow = head;
        ListNode fast = head;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        if (fast == null) {
            return head.next;
        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return head;
    }

    public ListNode removeNthFromEnd1(ListNode head, int n) {
        Stack<ListNode> stack = new Stack<>();
        ListNode p = head;
        while (p != null) {
            stack.push(p);
            p = p.next;
        }
        for (int i = 0; i < n; i++) {
            stack.pop();
        }
        if (stack.isEmpty()) {
            return head.next;
        }
        ListNode peek = stack.peek();
        peek.next = peek.next.next;
        return head;
    }

}
